首页 > 试题广场 >

矩形覆盖

[编程题]矩形覆盖
  • 热度指数：607528 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？

数据范围：
进阶：空间复杂度 ，时间复杂度

注意：约定 n == 0 时，输出 0

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：


输入描述:
2*1的小矩形的总个数n


输出描述:
覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)
示例1

输入

0

输出

0
示例2

输入

1

输出

1
示例3

输入

4

输出

5
算法知识视频讲解
添加回答
推荐
Follow头像 Follow
依旧是斐波那契数列
2*n的大矩形，和n个2*1的小矩形
其中target*2为大矩阵的大小
有以下几种情形：
1⃣️target <= 0 大矩形为<= 2*0,直接return 1；
2⃣️target = 1大矩形为2*1，只有一种摆放方法，return1；
3⃣️target = 2 大矩形为2*2，有两种摆放方法，return2；
4⃣️target = n 分为两步考虑：
        第一次摆放一块 2*1 的小矩阵，则摆放方法总共为f(target - 1)
√






√







第一次摆放一块1*2的小矩阵，则摆放方法总共为f(target-2)
因为，摆放了一块1*2的小矩阵（用√√表示），对应下方的1*2（用××表示）摆放方法就确定了，所以为f(targte-2)
√ √





× ×






代码：
public class Solution {
    public int rectCover(int target) {
      if(target  <= 1){
			return 1;
		}
        if(target*2 == 2){
            return 1;
        }else if(target*2 == 4){
            return 2;
        }else{
            return rectCover((target-1))+rectCover(target-2);
        }
    }
}

编辑于 2015-12-12 12:08:02 回复(87)
Python 3
曰无衣bupt头像 曰无衣bupt
其实就是变相的斐波那契。 
class Solution:
    def rectCover(self , number: int) -> int:
        # write code here
        # 这不又是个斐波那契吗
        if not number:
            return 0
        l = [1,2,3,5]
        i = 4
        while len(l) < number:
            l.append(l[i-1]+l[i-2])
            i += 1
        return l[number-1]


发表于 2022-06-16 17:17:40 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    # 符合斐波那契数列
    def rectCover(self , number: int) -> int:
        if number <= 2:
            return number
        a = 1
        b = 2
        for i in range(3, number + 1):
            res = a + b 
            a = b 
            b = res
        return res
发表于 2022-05-11 16:21:42 回复(0)
Python 3
Yyyzs头像 Yyyzs 
class Solution:
    def rectCover(self , number: int) -> int:
        # write code here
        
        if number < 3:
            return number
        
        res = self.mySolution1(number)
        
        return res
    
    def mySolution2(self, number):
        # 递归-O(n^2)O(n) 算上递归空间占用
        # python递归超时
        def rec(num):
            if num < 1:
                return 0
            elif num < 3:  # 如果不限制 return 0 的话就会无限循环下去gg
                return num
            else:
                return rec(num-1) + rec(num-2)
        
        res = rec(number)
        
        return res
        
    def mySolution1(self, number):
        # 动态规划-O(n)O(1)
        pre,mid,order = 1, 2, 0
        res = 0
        
        for i in range(3, number+1):
            order = mid + pre
            pre = mid
            mid = order
            
            if order > res:
                res = order
        
        return res
        
        
    def mySolution(self, number):
        # 动态规划-O(n)O(n)
        
        dp = [0]*(number+1)
        dp[0], dp[1], dp[2] = 0, 1, 2
        
        for i in range(3, number+1):
            dp[i] = dp[i-2] + dp[i-1]
        
        return dp[-1]

发表于 2022-03-17 21:52:56 回复(0)
Python 3
牛客800980914号头像 牛客800980914号 
# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, n):
        # write code here
        res = {0:0,1:1,2:2}
        for i in range(3,n+1):
            res[i] = res[i-1] + res[i-2]
        return res[n]

发表于 2021-09-15 13:20:42 回复(0)
Python 3
今天没有作业写头像 今天没有作业写
依然是斐波那契数列的变形问题 
class Solution:
    def rectCover(self, number):
        # write code here
        res = [0,1,2,3]
        for number in range(4,number+1):
            if number == len(res):
                res.append(res[number-1]+res[number-2])
        return res[number]


发表于 2021-08-22 17:30:26 回复(0)
Python 3
时光他与猫头像 时光他与猫
# -*- coding:utf-8 -*-
# 我这样做算是动态规划吗？

class Solution:
    def rectCover(self, number):
        # write code here
        if number == 0:
            return 0
        if number == 1:
            return 1
        if number >= 2:
            a = 1
            b = 1
            ret = 0
            for i in range(number-1):
                ret = a + b
                b = a
                a = ret
            return ret
发表于 2021-08-22 13:41:59 回复(0)
Python 3
可恶，被他装到了头像 可恶，被他装到了
# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        if number < 1:
            return 0
        elif number < 4:
            return number
        else:
            list = [2,3]
            for i in range(4,number+1):
                newvalue = list[0] + list[1]
                list = [list[1],newvalue]
            return list[-1]
        # write code here
发表于 2021-08-16 12:32:33 回复(0)
Python 3
三水123头像 三水123
class Solution:
    def rectCover(self, number):
        # write code here
        res = [0, 1, 2]
        while len(res)<=number:
            res.append(res[-1]+res[-2])
        return res[number]
发表于 2021-08-13 11:44:53 回复(0)
Python 3
tantantansq头像 tantantansq 
# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number<=2:
            return number
        a=1
        b=2
        for i in range(number-2):
            a,b=b,a+b 
        return b

发表于 2021-08-09 00:59:58 回复(0)
Python 3
阿司匹林Yo头像 阿司匹林Yo 
class Solution:
    def rectCover(self, number):
        if number <= 2:
            return number
        num1, num2 = 1, 2
        for _ in range(number-2):
            num2 += num1
            num1 = num2 - num1
        return num2

发表于 2021-07-31 08:39:07 回复(0)
提交观点

问题信息

动态规划 递归
来自：开发工程师&系统架构高...
难度：
11条回答 149142浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号